|
In mathematics and computer science, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined together in a feedback-free manner (called a "wreath product" or "cascade"). Krohn and Rhodes found a general decomposition for finite automata. In doing their research, though, the authors discovered and proved an unexpected major result in finite semigroup theory, revealing a deep connection between finite automata and semigroups. ==Definitions and description of the Krohn–Rhodes theorem == A semigroup ''S'' that is a homomorphic image of a subsemigroup of ''T'' is said to be a divisor of ''T''. The Krohn–Rhodes theorem for finite semigroups states that every finite semigroup ''S'' is a divisor of a finite alternating wreath product of finite simple groups, each a divisor of ''S'', and finite aperiodic semigroups (which contain no nontrivial subgroups).〔Holcombe (1982) pp.141-142〕 In the automata formulation, the Krohn–Rhodes theorem for finite automata states that given a finite automaton ''A'' with states ''Q'' and input set ''I'', output alphabet ''U'', then one can expand the states to ''Q' '' such that the new automaton ''A' '' embeds into a cascade of "simple", irreducible automata: In particular, ''A'' is emulated by a feed-forward cascade of (1) automata whose transitions semigroups are finite simple groups and (2) automata which are banks of flip-flops running in parallel.〔The flip-flop is the two-state automaton with three input operations: the identity (which leaves its state unchanged) and the two reset operations (which overwrite the current state by a resetting to a particular one of the two states). This can be considered a one-bit read-write storage unit: the identity corresponds to reading the bit (while leaving its value unaltered), and the two resets to setting the value of the bit to 0 or 1. Note that a reset is an irreversible operator as it destroys the currently stored bit value. NB: The semigroup of the flip-flop and all its subsemigroups are irreducible.〕 The new automaton ''A' '' has the same input and output symbols as ''A''. Here, both the states and inputs of the cascaded automata have a very special hierarchical coordinate form. Moreover, each simple group (''prime'') or non-group irreducible semigroup (subsemigroup of the flip-flop monoid) that divides the transformation semigroup of ''A'' must divide the transition semigroup of some component of the cascade, and only the primes that must occur as divisors of the components are those that divide ''A'' 's transition semigroup. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Krohn–Rhodes theory」の詳細全文を読む スポンサード リンク
|